SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Multi-commodity flow problem</title>

</head>

Multi-commodity flow problem

</h1>

</header>

The multi-commodity flow problem is a <a href="Network_flow_problem" title="Network flow problem">network flow problem</a> with multiple commodities (flow demands) between different source and sink nodes.

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

Given a <a href="Flow_network" title="Flow network">flow network</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \,G(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \,G(V,E)}</annotation>

</semantics>

</math><img src="./fd8f726b8c111a728114a99076af44093b3485e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.62ex; height:2.843ex;" alt="{\displaystyle \,G(V,E)}" loading="lazy">, where edge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (u,v)\in E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (u,v)\in E}</annotation>

</semantics>

</math><img src="./fb3670c33f5481059c095a58c9ebbd60dc6f35f8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.917ex; height:2.843ex;" alt="{\displaystyle (u,v)\in E}" loading="lazy"> has capacity <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \,c(u,v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \,c(u,v)}</annotation>

</semantics>

</math><img src="./5ef051d0bdf9ea28b0eb4e30df748dfd955ba6d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.694ex; height:2.843ex;" alt="{\displaystyle \,c(u,v)}" loading="lazy">. There are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \,k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \,k}</annotation>

</semantics>

</math><img src="./dd87d8e0613318763177b62703ceed34630f4d60.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.598ex; height:2.176ex;" alt="{\displaystyle \,k}" loading="lazy"> commodities <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{1},K_{2},\dots ,K_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{1},K_{2},\dots ,K_{k}}</annotation>

</semantics>

</math><img src="./6816e92e29952f09476c4a915eec2ae23d067715.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.328ex; height:2.509ex;" alt="{\displaystyle K_{1},K_{2},\dots ,K_{k}}" loading="lazy">, defined by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \,K_{i}=(s_{i},t_{i},d_{i})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \,K_{i}=(s_{i},t_{i},d_{i})}</annotation>

</semantics>

</math><img src="./9e54e2c8c28ddb1b2a447b4fcd85dd356c49c9b3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.673ex; height:2.843ex;" alt="{\displaystyle \,K_{i}=(s_{i},t_{i},d_{i})}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \,s_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \,s_{i}}</annotation>

</semantics>

</math><img src="./d93743825c3be76d42a5702ee003e730d4012d23.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.277ex; height:2.009ex;" alt="{\displaystyle \,s_{i}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \,t_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \,t_{i}}</annotation>

</semantics>

</math><img src="./191154186ab6bf3233930f657def24a9f84efc9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.026ex; height:2.343ex;" alt="{\displaystyle \,t_{i}}" loading="lazy"> is the source and sink of commodity <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \,i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \,i}</annotation>

</semantics>

</math><img src="./9f624ef21533c20e2a78b1e22f156069a6689c0c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.19ex; height:2.176ex;" alt="{\displaystyle \,i}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \,d_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \,d_{i}}</annotation>

</semantics>

</math><img src="./359df4717b5baf74e94d96794e087a18946d39e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.396ex; height:2.509ex;" alt="{\displaystyle \,d_{i}}" loading="lazy"> is its demand. The variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \,f_{i}(u,v)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \,f_{i}(u,v)}</annotation>

</semantics>

</math><img src="./867d8d814a9eb1c7a94e78524ae381c22eaf19df.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.627ex; height:2.843ex;" alt="{\displaystyle \,f_{i}(u,v)}" loading="lazy"> defines the fraction of flow <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \,i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \,i}</annotation>

</semantics>

</math><img src="./9f624ef21533c20e2a78b1e22f156069a6689c0c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.19ex; height:2.176ex;" alt="{\displaystyle \,i}" loading="lazy"> along edge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \,(u,v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \,(u,v)}</annotation>

</semantics>

</math><img src="./f9a0e309c3fb6dc235a9ceedac25497fecdb9580.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.688ex; height:2.843ex;" alt="{\displaystyle \,(u,v)}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \,f_{i}(u,v)\in [0,1]}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \,f_{i}(u,v)\in [0,1]}</annotation>

</semantics>

</math><img src="./f1b22ad501243e487bf55c1322acfcb8592eb051.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.12ex; height:2.843ex;" alt="{\displaystyle \,f_{i}(u,v)\in [0,1]}" loading="lazy"> in case the flow can be split among multiple paths, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \,f_{i}(u,v)\in \{0,1\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \,f_{i}(u,v)\in \{0,1\}}</annotation>

</semantics>

</math><img src="./659d150ff24abfe3ad404fa585b21678dc0fcbd4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.151ex; height:2.843ex;" alt="{\displaystyle \,f_{i}(u,v)\in \{0,1\}}" loading="lazy"> otherwise (i.e. "single path routing"). Find an assignment of all flow variables which satisfies the following four constraints:

(1) Link capacity: The sum of all flows routed over a link does not exceed its capacity.

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall (u,v)\in E:\,\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}\leq c(u,v)}</annotation>

</semantics>

</math><img src="./c78b8efd54c96c643320b3706ca8ef29064f37e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:37.609ex; height:7.343ex;" alt="{\displaystyle \forall (u,v)\in E:\,\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}\leq c(u,v)}" loading="lazy"></dd></dl>

(2) Flow conservation on transit nodes: The amount of a flow entering an intermediate node <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</math><img src="./c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" loading="lazy"> is the same that exits the node.

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(u,w)\in E}f_{i}(u,w)-\sum _{(w,u)\in E}f_{i}(w,u)=0\quad \mathrm {when} \quad u\neq s_{i},t_{i}}</annotation>

</semantics>

</math><img src="./faedbb7189b6ad4337e870a42e89d86cd8bff816.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:71.907ex; height:6.009ex;" alt="{\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(u,w)\in E}f_{i}(u,w)-\sum _{(w,u)\in E}f_{i}(w,u)=0\quad \mathrm {when} \quad u\neq s_{i},t_{i}}" loading="lazy"></dd></dl>

(3) Flow conservation at the source: A flow must exit its source node completely.

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(u,w)\in E}f_{i}(s_{i},w)-\sum _{(w,u)\in E}f_{i}(w,s_{i})=1}</annotation>

</semantics>

</math><img src="./8ed049e43c4059d9f30eecd70cce7139d5a35f2b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:54.096ex; height:6.009ex;" alt="{\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(u,w)\in E}f_{i}(s_{i},w)-\sum _{(w,u)\in E}f_{i}(w,s_{i})=1}" loading="lazy"></dd></dl>

(4) Flow conservation at the destination: A flow must enter its sink node completely.

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(u,w)\in E}f_{i}(w,t_{i})-\sum _{(w,u)\in E}f_{i}(t_{i},w)=1}</annotation>

</semantics>

</math><img src="./c91d3222b088ccf48a8c46d8731c8c02e0eca6b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:53.594ex; height:6.009ex;" alt="{\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(u,w)\in E}f_{i}(w,t_{i})-\sum _{(w,u)\in E}f_{i}(t_{i},w)=1}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Corresponding_optimization_problems">Corresponding optimization problems</h2></div>

Load balancing is the attempt to route flows such that the utilization <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U(u,v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U(u,v)}</annotation>

</semantics>

</math><img src="./54445e9000689bc2031c4bf98139d94b78658d98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.083ex; height:2.843ex;" alt="{\displaystyle U(u,v)}" loading="lazy"> of all links <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (u,v)\in E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (u,v)\in E}</annotation>

</semantics>

</math><img src="./fb3670c33f5481059c095a58c9ebbd60dc6f35f8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.917ex; height:2.843ex;" alt="{\displaystyle (u,v)\in E}" loading="lazy"> is even, where

<mfrac>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U(u,v)={\frac {\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}}{c(u,v)}}}</annotation>

</semantics>

</math><img src="./e35cf9f559261c8cc2392bc37dc8ae6d5d7bd0df.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:27.686ex; height:7.009ex;" alt="{\displaystyle U(u,v)={\frac {\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}}{c(u,v)}}}" loading="lazy"></dd></dl>

The problem can be solved e.g. by minimizing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{u,v\in V}(U(u,v))^{2}}">

</mrow>

</munder>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{u,v\in V}(U(u,v))^{2}}</annotation>

</semantics>

</math><img src="./0cb58e5973eb3f0f5d72816375df3d4beb0612ac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:14.502ex; height:5.843ex;" alt="{\displaystyle \sum _{u,v\in V}(U(u,v))^{2}}" loading="lazy">. A common linearization of this problem is the minimization of the maximum utilization <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{max}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{max}}</annotation>

</semantics>

</math><img src="./7d755450de4a2a118d210708681c2eb199dd3788.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.072ex; height:2.509ex;" alt="{\displaystyle U_{max}}" loading="lazy">, where

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall (u,v)\in E:\,U_{max}\geq U(u,v)}</annotation>

</semantics>

</math><img src="./d51b86b4cc20236f92ec66a7c2b0fc20af12b3aa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.788ex; height:2.843ex;" alt="{\displaystyle \forall (u,v)\in E:\,U_{max}\geq U(u,v)}" loading="lazy"></dd></dl>

In the minimum cost multi-commodity flow problem, there is a cost <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a(u,v)\cdot f(u,v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a(u,v)\cdot f(u,v)}</annotation>

</semantics>

</math><img src="./78bb299cbda94b5b5f6399fdd6e9ca95d7d34891.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.789ex; height:2.843ex;" alt="{\displaystyle a(u,v)\cdot f(u,v)}" loading="lazy"> for sending a flow on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \,(u,v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \,(u,v)}</annotation>

</semantics>

</math><img src="./f9a0e309c3fb6dc235a9ceedac25497fecdb9580.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.688ex; height:2.843ex;" alt="{\displaystyle \,(u,v)}" loading="lazy">. You then need to minimize

</mrow>

</munder>

<mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{(u,v)\in E}\left(a(u,v)\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}\right)}</annotation>

</semantics>

</math><img src="./386598bf33d96173039c9caaa535ffa0d249d618.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:31.481ex; height:7.843ex;" alt="{\displaystyle \sum _{(u,v)\in E}\left(a(u,v)\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}\right)}" loading="lazy"></dd></dl>

In the maximum multi-commodity flow problem, the demand of each commodity is not fixed, and the total throughput is maximized by maximizing the sum of all demands <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{i=1}^{k}d_{i}}">

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i=1}^{k}d_{i}}</annotation>

</semantics>

</math><img src="./79dd783ce8ff7ae7a33d1259112ded4d184d914d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:5.751ex; height:7.343ex;" alt="{\displaystyle \sum _{i=1}^{k}d_{i}}" loading="lazy">

<div class="mw-heading mw-heading2"><h2 id="Relation_to_other_problems">Relation to other problems</h2></div>

The minimum cost variant of the multi-commodity flow problem is a generalization of the <a href="Minimum_cost_flow_problem" class="mw-redirect" title="Minimum cost flow problem">minimum cost flow problem</a> (in which there is merely one source <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> and one sink <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">). Variants of the <a href="Circulation_problem" title="Circulation problem">circulation problem</a> are generalizations of all flow problems. That is, any flow problem can be viewed as a particular circulation problem.<a href="#cite_note-ahuja_et_al_1993-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Usage">Usage</h2></div>

<a href="Routing_and_wavelength_assignment" title="Routing and wavelength assignment">Routing and wavelength assignment</a> (RWA) in <a href="Optical_burst_switching" title="Optical burst switching">optical burst switching</a> of <a href="SONET" class="mw-redirect" title="SONET">Optical Network</a> would be approached via multi-commodity flow formulas, if the network is equipped with wavelength conversion at every node.

<a href="Register_allocation" title="Register allocation">Register allocation</a> can be modeled as an integer minimum cost multi-commodity flow problem: Values produced by instructions are source nodes, values consumed by instructions are sink nodes and registers as well as stack slots are edges.<a href="#cite_note-2">[2]</a>

<div class="mw-heading mw-heading2"><h2 id="Solutions">Solutions</h2></div>

In the decision version of problems, the problem of producing an integer flow satisfying all demands is <a href="NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a>,<a href="#cite_note-EIS76-3">[3]</a> even for only two commodities and unit capacities (making the problem <a href="Strongly_NP-complete" class="mw-redirect" title="Strongly NP-complete">strongly NP-complete</a> in this case).

If fractional flows are allowed, the problem can be solved in polynomial time through <a href="Linear_programming" title="Linear programming">linear programming</a>,<a href="#cite_note-4">[4]</a> or through (typically much faster) <a href="Fully_polynomial_time_approximation_scheme" class="mw-redirect" title="Fully polynomial time approximation scheme">fully polynomial time approximation schemes</a>.<a href="#cite_note-5">[5]</a>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

Multicommodity flow is applied in the overlay routing in content delivery.<a href="#cite_note-6">[6]</a>

<div class="mw-heading mw-heading2"><h2 id="External_resources">External resources</h2></div>

<ul><li>Papers by Clifford Stein about this problem: <a rel="nofollow" class="external free" href="http://www.columbia.edu/~cs2035/papers/#mcf">http://www.columbia.edu/~cs2035/papers/#mcf</a></li>

<li>Software solving the problem: <a rel="nofollow" class="external free" href="https://web.archive.org/web/20130306031532/http://typo.zib.de/opt-long_projects/Software/Mcf/">https://web.archive.org/web/20130306031532/http://typo.zib.de/opt-long_projects/Software/Mcf/</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFAhujaMagnantiOrlin1993" class="citation book cs1">Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Network Flows. Theory, Algorithms, and Applications. Prentice Hall.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFKoes2009" class="citation thesis cs1">Koes, David Ryan (2009). "Towards a more principled compiler: Register allocation and instruction selection revisited" (PhD). Carnegie Mellon University. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:26416771">26416771</a>.</cite>

</li>

<li id="cite_note-EIS76-3"><a href="#cite_ref-EIS76_3-0">^</a> <cite id="CITEREFS._Even_and_A._Itai_and_A._Shamir1976" class="citation journal cs1">S. Even and A. Itai and A. Shamir (1976). "On the Complexity of Timetable and Multicommodity Flow Problems". SIAM Journal on Computing. 5 (4). SIAM: 691–703. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0205048">10.1137/0205048</a>.</cite><cite id="CITEREFEvenItaiShamir1975" class="citation book cs1">Even, S.; Itai, A.; Shamir, A. (1975). "On the complexity of time table and multi-commodity flow problems". 16th Annual Symposium on Foundations of Computer Science (SFCS 1975). pp. 184–193. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.1975.21">10.1109/SFCS.1975.21</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:18449466">18449466</a>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFThomas_H._Cormen,_Charles_E._Leiserson,_Ronald_L._Rivest,_and_Clifford_Stein2009" class="citation book cs1"><a href="Thomas_H._Cormen" title="Thomas H. Cormen">Thomas H. Cormen</a>, <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Charles E. Leiserson</a>, <a href="Ronald_L._Rivest" class="mw-redirect" title="Ronald L. Rivest">Ronald L. Rivest</a>, and <a href="Clifford_Stein" title="Clifford Stein">Clifford Stein</a> (2009). "29". <a href="Introduction_to_Algorithms" title="Introduction to Algorithms">Introduction to Algorithms</a> (3rd ed.). MIT Press and McGraw–Hill. p. 862. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-262-03384-8</bdi>.</cite><code class="cs1-code">{{cite book}}</code>: CS1 maint: multiple names: authors list (link)

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFGeorge_Karakostas2002" class="citation conference cs1">George Karakostas (2002). <a rel="nofollow" class="external text" href="https://archive.org/details/proceedingsofthi2002acms/page/166">"Faster approximation schemes for fractional multicommodity flow problems"</a>. Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/proceedingsofthi2002acms/page/166">166–173</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-89871-513-X</bdi>.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <a rel="nofollow" class="external text" href="https://www.sigcomm.org/sites/default/files/ccr/papers/2015/July/0000000-0000009.pdf">Algorithmic Nuggets in Content Delivery</a> sigcomm.org

</li>

</ol></div>

Add: Jean-Patrice Netter, Flow Augmenting Meshings: a primal type of approach to the maximum integer flow in a multi-commodity network, Ph.D dissertation Johns Hopkins University, 1971

</div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-11-19" href="https://en.wikipedia.org/wiki/?title=Multi-commodity_flow_problem&oldid=1258472315">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>